package P1线性结构.LeetCode单调栈与单调队列;

import java.util.LinkedList;

public class LC42 {
    public int trap(int[] height) {
        LinkedList<Integer> stack = new LinkedList<>();
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int w = i - left - 1;
                int h = Math.min(height[i], height[left]) - height[top];
                sum += w * h;
            }
            stack.push(i);
        }
        return sum;
    }
}